// https://leetcode.cn/problems/single-number-ii/

// 题干：给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。
//       请你找出并返回那个只出现了一次的元素。
//       你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

// 碎语：时间复杂度O(N)，空间复杂度O(1)
//       还是利用异或性质
//       往细微处看，每一个比特位上，出现三次，那么这个出现一次的数的该比特位不管是0还是1
//       模上3之后还是原来的数

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int singleNumber(vector<int>& nums)
    {
        // 一共有32位
        int ret = 0;
        for (int i = 0 ; i < 32 ; i++){
            // 遍历数组中的每个数字
            int sum = 0; // 当前比特位所有数字之和
            for (int j = 0 ; j < nums.size() ; j++) {
                // 判断当前位为0还是1
                int digit = (nums[j] >> i) & 1;
                sum += digit;
                sum %= 3; // 此时要么为0，要么为1
            }
            ret |= sum << i; // 返回给最终结果
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {0,1,0,1,0,1,99};

    cout << sol.singleNumber(nums) << endl;

    return 0;
}